/*
完全背包问题
*/
#include <vector>
using namespace std;

int knap_dp(const std::vector<int> &w, const std::vector<int> &v, int cap) {
  int n = w.size();
  // 初始化 dp 表
  std::vector<std::vector<int>> dp(n + 1, std::vector<int>(cap + 1, 0));
  for (int i = 1; i <= n; i++) {
    for (int c = 1; c <= cap; c++) {
      // 背包容量 小于当前物品容量
      if (c < w[i - 1]) {
        dp[i][c] = dp[i - 1][c];
      } else {
        dp[i][c] = std::max(dp[i - 1][c], dp[i][c - w[i - 1]] + v[i - 1]);
      }
    }
  }
  return dp[n][cap];
}
/*
空间优化
*/
int knap_dp_space(const std::vector<int> &w, const std::vector<int> &v,
                  int cap) {
  int n = w.size();
  // 初始化 dp 表
  std::vector<int> dp(n + 1, 0);
  for (int i = 1; i <= n; i++) {
    for (int c = 1; c <= cap; c++) {
      // 背包容量 小于当前物品容量
      if (c < w[i - 1]) {
        dp[c] = dp[c];
      } else {
        dp[c] = std::max(dp[c], dp[c - w[i - 1]] + v[i - 1]);
      }
    }
    dp[0] = dp[1];
  }
  return dp[n];
}